class Solution {
public:
    string LCS(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        int end = 0;
        int maxlen = 0;
        vector<vector<int>> dp(m+1, vector<int>(n, 0));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    maxlen = max(maxlen, dp[i][j]);
                    if (maxlen == dp[i][j]) {
                        end = i-1;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return s1.substr(end-maxlen+1, maxlen);
    }
};